/*给定两个字符串s1和s2，写一个函数来判断s2是否包含s1的排列。换句话说，第一个字符串的排列之一是第二个字符串的子串。
*
* 输入: s1 = "ab" s2 = "eidbaooo"
* 输出: True
* 解释: s2 包含 s1 的排列之一 ("ba").
* */

package plan_study.sixth;

import java.util.*;

public class leetcode567 {

    public static void main(String[] args) {

        leetcode567 obj = new leetcode567();
        String s1 = "adc";
        String s2 = "dcda";
        System.out.println(obj.checkInclusion(s1, s2));
    }

    //暴力超时
//    public boolean checkInclusion(String s1, String s2){
//
//        String[] res1 = s1.split("");
//        Arrays.sort(res1);
//        for (int i = 0;i <= s2.length() - s1.length();i++){
//            String s = s2.substring(i, i + s1.length());
//            String[] res2 = s.split("");
//            Arrays.sort(res2);
//            if (Arrays.toString(res1).equals(Arrays.toString(res2))){
//                return true;
//            }
//        }
//        return false;
//    }

    public boolean checkInclusion(String s1, String s2){

        int len1 = s1.length(), len2 = s2.length();
        if (len1 > len2){
            return false;
        }
        int[] ans = new int[26];
        for (int i = 0;i < len1;i++){
            ans[s1.charAt(i) - 'a']++;
            ans[s2.charAt(i) - 'a']--;
        }
        int diff = 0;
        for (int i : ans){
            if (i != 0){
                diff++;
            }
        }
        if (diff == 0){
            return true;
        }
        for (int j = len1;j < len2;j++){
            int m = s2.charAt(j) - 'a', n = s2.charAt(j - len1) - 'a';
            if (m == n){
                continue;
            }
            if (ans[m] == 0){
                diff++;
            }
            ans[m]--;
            if (ans[m] == 0){
                diff--;
            }
            if (ans[n] == 0){
                diff++;
            }
            ans[n]++;
            if (ans[n] == 0){
                diff--;
            }
            if (diff == 0){
                return true;
            }
        }
        return false;
    }
}
